UVa/12322 - Handgun Shooting Sport/12322.2.cpp

   1 // Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <bitset>
  14 #include <string>
  15 #include <cstdio>
  16 #include <vector>
  17 #include <cmath>
  18 #include <queue>
  19 #include <deque>
  20 #include <stack>
  21 #include <list>
  22 #include <map>
  23 #include <set>
  24
  25 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define D(x) cout << #x " is " << x << endl
  28
  29
  30 struct point {
  31     int x, y;
  32     point(){} point(int x, int y) : x(x), y(y) {}
  33     bool operator < (const point &t) const {
  34         return x * t.y - y * t.x > 0;
  35     }
  36     bool operator == (const point &t) const {
  37         return x * t.y - y * t.x == 0;
  38     }
  39     bool operator <= (const point &t) const {
  40         return *this < t or *this == t;
  41     }
  42     bool operator != (const point &t) const {
  43         return !(*this == t);
  44     }
  45 };
  46
  47 typedef pair< point, point > interval;
  48
  49 // Returns true if interval 'a' is strictly included in interval 'b'
  50 bool included(const interval &a, const interval &b) {
  51     return b.first < a.first and a.second < b.second;
  52 }
  53
  54 const int MAXN = 1001;
  55
  56 interval intervals[MAXN];
  57 int B;
  58
  59 void delete_redundant() {
  60     bitset<MAXN> deleted;
  61     for (int i = 0; i < B; ++i) {
  62         for (int j = 0; j < B; ++j) {
  63             // delete interval i if interval j is completely inside it
  64             if (included(intervals[j], intervals[i])) {
  65                 deleted[i] = true;
  66                 break;
  67             }
  68         }
  69     }
  70     int k = 0;
  71     for (int i = 0; i < B; ++i) {
  72         if (!deleted[i]) {
  73             intervals[k++] = intervals[i];
  74         }
  75     }
  76     B = k;
  77 }
  78
  79 int main(){
  80     while (cin >> B) {
  81         if (B == 0) break;
  82         for (int i = 0; i < B; ++i) {
  83             point p1, p2;
  84             cin >> p1.x >> p1.y >> p2.x >> p2.y;
  85             assert(p1 != p2);
  86             if (p2 < p1) swap(p1, p2);
  87             intervals[i] = make_pair( p1, p2 );
  88         }
  89         //printf("Before removing redundant B is %d\n", B);
  90         delete_redundant();
  91         sort(intervals, intervals + B);
  92         //printf("After removing redundant B is %d\n", B);
  93
  94         //printf("Before removing duplicates B is %d\n", B);
  95         B = unique(intervals, intervals + B) - intervals;
  96         //printf("After removing duplicates B is %d\n", B);
  97
  98         int ans = 0, i = 0;
  99         while (i < B) {
 100             ans++;
 101             point pick = intervals[i].second;
 102             while (i < B and intervals[i].first <= pick) i++;
 103         }
 104         printf("%d\n", ans);
 105     }
 106     return 0;
 107 }